﻿#include <iostream>
#include <stdlib.h>
#include <string>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

class Solution {
public:
	vector<string> ans;
	unordered_map<char, string> phone{
		{'2', "abc"},
		{'3', "def"},
		{'4', "ghi"},
		{'5', "jkl"},
		{'6', "mno"},
		{'7', "pqrs"},
		{'8', "tuv"},
		{'9', "wxyz"}
	};
	void dfs(string digits, int cur, string &comb) {
		if (cur == digits.size())
			ans.push_back(comb);
		string key = phone[digits[cur]];
		for (int i = 0; i < key.size(); i++) {
			comb += key[i];
			dfs(digits, cur + 1, comb);
			comb.pop_back();
		}
	}
	vector<string> letterCombinations(string digits) {
		string comb;
		dfs(digits, 0, comb);
		return ans;
	}
};

int main()
{
	Solution sol;
	string test = "32";
	sol.letterCombinations(test);
	cout <<endl;
}
